/* NoX (NoC Simulator)
 *
 * Dept. of Computer Science & Engineering, Pennsylvania State University.
 * All Rights Reserved.
 *  
 * 1. License     
 * NoX is distributed free of charge for academic, educational, noncommercial 
 * research purposes as long as this notice in its entirety is preserved in
 * every file included in this package.
 * All commercial use of this program requires separate licence. Contact the
 * author for details.
 * 
 * 2. All the publications that used the simulation results generated by the 
 * NoX should notify the author of the publication information and put 
 * following reference.
 *
 *  http://www.cse.psu.edu/~dpark/nox/
 * 
 * 3. Modification of the source code is permitted and encouraged as long as 
 * it follows the terms described in this copyright notice.
 *
 * 4. The author is not responsible for any problems caused by possible errors
 * of the NoX package. Therefore, users should verify the simulation result
 * before using it in their publication.
 *
 * Dept. of Computer Science & Engineering, Pennsylvania State University.
 * Contact: dpark@cse.psu.edu 
 * 
 * 6. If problems are found with the NoX package, please send an email to the
 * author for discussion and correction.

 */

/* Update History
 *
 * Jan. 31, 2006  Version 1.0 released by Dongkook Park 
 *
 */

/* ROUTE_PROXIMITY_AWARE.C - Implements the proximity aware routing algorithm */

#include <stdlib.h>
#include "main.h"
#include "router_common.h"
#include "route_proximity_aware.h"
#include "shared.h"

void init_FA_route_info(void)
{
  int row, col;
  int current_node;
  int nneighbor[4];
  int n_failed_neighbor;
  int n_edge_neighbor;
  int i,j;
  int status;

  //        1          0:LEFT
  //        |          1:UP 
  //    0 - 4 - 2      2:RIGHT
  //        |          3:DOWN 
  //        3          4:THIS
  //  HEALTHY : 1 input and 3 output paths available  
  //  GOOD    : 1 input and 2 output paths available
  //  BAD     : 1 input and 1 output path available
  //  WORSE   : 1 input and 0 output path available 
  //  TRAPPED : no input/output path available

  for(row=0; row < MESH_NUM_ROWS; row++)
  {
    for(col=0; col < MESH_NUM_COLS; col++) 
    {
      n_edge_neighbor=0;
      n_failed_neighbor=0;
      current_node = (row * MESH_NUM_COLS) + col;
      if( router[current_node].health_status != FAIL ) 
      {
        // Initialize FA_blocked_info[]
        for(i=LEFT; i<=DOWN; i++) 
        {
          nneighbor[i] = neighbor[current_node][i];
          router[current_node].FA_blocked_info[i] = NOBLOCK;
        }

        // Count the number of edges of this node.
        // And mark blocked direction in FA_blocked_info[].
        for(i=LEFT; i<= DOWN; i++)
          if(nneighbor[i] == EDGE)
          {
            router[current_node].FA_blocked_info[i] = BLOCK;
            n_edge_neighbor++;
          }

        // Count the number of failed neighbor of this node.
        // Here, if the link to the neighbor is fail, regard this neighbor as fail 
        // since no data can be transferred to this neighbor.
        // And mark blocked direction in FA_blocked_info[].
        for(i=LEFT; i<= DOWN; i++)
          if( nneighbor[i] != EDGE )
	    if(router[nneighbor[i]].health_status == FAIL ||
	       router[current_node].FA_link_info[i] == FAIL ) 
	    {
	      router[current_node].FA_blocked_info[i] = BLOCK;
	      n_failed_neighbor++;
	    }

        // If the sum of the edges and failed neighbor equals 4, 
        // this node is trapped node. Mark and continue to next node.
        // In this case, we don't need to set router[current_node].FA_route_info[] 
        // because this node cannot be reached from other nodes and thus, 
        // this information is meaningless. 
        if(n_failed_neighbor + n_edge_neighbor == 4)
        {
          router[current_node].health_status = TRAPPED;
          continue;
        }
        
        // Now, current node is neither a trapped node or a failed node.
        // i : input direction
        // j : output direction
        for(i=LEFT; i<=DOWN; i++)
        {
          // We don't need a input from the EDGE.
          if(nneighbor[i] == EDGE)
            continue;

          n_failed_neighbor = 0;
          n_edge_neighbor = 0;
            
          for(j=LEFT; j<= DOWN; j++)
          {
              // We consider only three directions other than input direction.
              // And the output direction should not be blocked(EDGE).
              if(i == j)
                continue;
              if(nneighbor[j] == EDGE)
              {
                n_edge_neighbor++;
                continue;
              }
              // Now, count the number of failed neighbors among non-edge neighbors
              // that are located in the direction other than input direction.
              // As before, if the link to the neighbor is fail, regard this neighbor
              // as fail since no data can be transferred to this neighbor.
              if(router[nneighbor[j]].health_status == FAIL || 
                 router[current_node].FA_link_info[j] == FAIL)
                n_failed_neighbor++;
            }// for j

            // Now, we have both the number of EDGE and the number of failed neighbors
            // of current node.  Set the routing information of current node.
            // The 'status' value is decided according to the number of available path
            // a flit can go from this node from the viewpoint of the input flit 
            // as described at the beginning of the function.
            switch(n_edge_neighbor)
            {
              case 0 : { // Middle node (all nodes except side nodes and corner nodes)
                         switch(n_failed_neighbor)
                         {
                           case 0:{status = HEALTHY; break;}
                           case 1:{status = GOOD;    break;}
                           case 2:{status = BAD;     break;}
                           case 3:{status = WORSE;   break;}
                         }// switch
                         break;
                       }// case 0
              case 1 : { // Side node (top-most,left-most,right-most,
                         // bottom-most nodes except corner nodes)
                         switch(n_failed_neighbor)
                         {
                           case 0:{status = GOOD;    break;}
                           case 1:{status = BAD;     break;}
                           case 2:{status = WORSE;   break;}
                         }// switch
                         break;
                       }// case 1
              case 2 : { // Corner node (0,7,56,63)
                         switch(n_failed_neighbor)
                         {
                           case 0:{status = BAD;     break;}
                           case 1:{status = WORSE;   break;}
                         }// switch
                         break;
                       }// case 2
            }// switch
            router[current_node].FA_route_info[i] = status; 
        }// for i
      }// if( router[current_node].health_status != FAIL ) 

      else
      {
          for(i=LEFT; i<=DOWN; i++)
              router[current_node].FA_route_info[i] = FAIL;
      }
    }// for col 
  }// for row
}

void init_FA_neighbor_info(void)
{
  int row, col;
  int current_node;
  int nneighbor[4];
  int i;
  int status;

  for(row=0; row < MESH_NUM_ROWS; row++)
  {
    for(col=0; col < MESH_NUM_COLS; col++) 
    {
      current_node = (row * MESH_NUM_COLS) + col;
      
      // If current node is either FAIL or TRAPPED state, skip current node 
      // since no routing request can be made to this node.
      status = router[current_node].health_status;
      if( status == FAIL || status == TRAPPED ) 
      {
          for(i=LEFT; i<=DOWN; i++) 
              router[current_node].FA_neighbor_info[i] = FAIL; 
          continue;
      }
      
      // Collect neighbor node number.
      for(i=LEFT; i<=DOWN; i++) 
        nneighbor[i] = neighbor[current_node][i];

      for(i=LEFT; i<=DOWN; i++) 
      {
        // Set the neighbor information.
        
        // If each neighbor is EDGE or in either FAIL or TRAPPED state,
        // or if the link between current node and neighbor node is fail,
        // we don't need to collect their state since we cannot send
        // flit to these node. Thus, set neighbor information as FAIL.
        status = router[nneighbor[i]].health_status;
        if( nneighbor[i] == EDGE || status == FAIL || status == TRAPPED ||
            router[current_node].FA_link_info[i] == FAIL)
          router[current_node].FA_neighbor_info[i] = FAIL; 

        // As described below, FA_neighbor_info[C][LEFT] contains the status
        // of left node when we think the flit is to be sent to the left node
        // from the right-side. Thus, we set it to FA_route_info[L][RIGHT]. 
        //        T          LEFT  0
        //        |          UP    1
        //    L - C - R      RIGHT 2
        //        |          DOWN  3
        //        B      
        // FA_neighbor_info[C][LEFT ] = FA_route_info[L][RIGHT]
        // FA_neighbor_info[C][UP   ] = FA_route_info[T][DOWN ]
        // FA_neighbor_info[C][RIGHT] = FA_route_info[R][LEFT ]
        // FA_neighbor_info[C][DOWN ] = FA_route_info[D][UP   ]
        else
          router[current_node].FA_neighbor_info[i] = router[nneighbor[i]].FA_route_info[(i+2)%4]; 
      }// for i

    }// for col
  }// for row
}

void init_FA_direction_info(void)
{
  int row, col;
  int current_node;
  int nneighbor[4];
  int i,j;
  int status;
  int rs, ns; // router status and neighbor status respectively.

  for(row=0; row < MESH_NUM_ROWS; row++)
  {
    for(col=0; col < MESH_NUM_COLS; col++) 
    {
      current_node = (row * MESH_NUM_COLS) + col;
      
      // Collect neighbor node number.
      for(i=LEFT; i<=DOWN; i++) 
        nneighbor[i] = neighbor[current_node][i];

      // If current node is either FAIL or TRAPPED state, skip current node 
      // since no routing request can be made to this node.
      // Actually, this can be omitted since FA_route_info[] and FA_blocked_info[]
      // are already set to FAIL in other two functions above.
      // FA_direction_info[][] will have value of 9 in this case.
//      status = router[current_node].health_status;
//      if( status == FAIL || status == TRAPPED ) 
//        continue;

      // Now, set priority information of every possible direction
      // We have 9 different priority value.
      // +----------+------------+----------+
      // | Priority | Neighbor   | NNeighbor|
      // +----------+------------+----------+
      // |  0       | Healthy    | Healthy  |
      // |  0       | Good       | Healthy  |
      // |  0       | Bad        | Healthy  |
      // |  1       | Healthy    | Good     |
      // |  1       | Good       | Good     |
      // |  1       | Bad        | Good     |
      // |  2       | Healthy    | Bad      |
      // |  2       | Good       | Bad      |
      // |  2       | Good       | Bad      |
      // |  3       | *          | Worse    |
      // |  3       | *          | Fail     |
      // +----------+------------+----------+
      for(i=LEFT; i<=DOWN; i++)
      {
        //rs = router[current_node].FA_route_info[i];
        rs = router[current_node].FA_neighbor_info[i];
        for(j=LEFT; j<=DOWN; j++)
        {
          // if the neighbor is unreachable, set status to 3.
          if(router[current_node].FA_blocked_info[j] == BLOCK)
              status = 3;
          else
          {
              //ns = router[current_node].FA_neighbor_info[j];  
              ns = router[nneighbor[i]].FA_neighbor_info[j];  
              if     ( rs == HEALTHY && ns == HEALTHY ) status = 0;//0;
              else if( rs == GOOD    && ns == HEALTHY ) status = 0;//1;
              else if( rs == BAD     && ns == HEALTHY ) status = 0;//2;
              else if( rs == HEALTHY && ns == GOOD    ) status = 1;//2;
              else if( rs == GOOD    && ns == GOOD    ) status = 1;//3;
              else if( rs == BAD     && ns == GOOD    ) status = 1;//3;
              else if( rs == HEALTHY && ns == BAD     ) status = 2;//4;
              else if( rs == GOOD    && ns == BAD     ) status = 2;//5;
              else if( rs == BAD     && ns == BAD     ) status = 2;//6;
              else status = 3; // rs == BAD && ns == BAD
          }// else

          // Now, status can have value between 0 and 9 where small number
          // means higher priority.
          // router[cnode].FA_direction_info[dir1][dir2] means the priority of the path
	  // from cnode to a neighbor1 in dir1 direction from cnode and to a neighbor2, 
	  // which is the neighbor of neighbor1 in dir2 direction from neighbor1.
	  // 
          // Ex) router[cnode].FA_direction_info[LEFT][DOWN]
	  //
	  // (neighbor 1) 0 <----- 0(cnode)
	  //              |   LEFT
	  //         DOWN |
	  //              v
	  // (neighbor 2) 0
	  //
	  // The status value will be calculated based on the status of both neighbor 1 and 2
	  // as shown above.
	  //
          // This information is used for routing a flit in proximity_aware_route() function.
          router[current_node].FA_direction_info[i][j] = status;
        }// for j
      }// for i
    }// for col
  }// for row
}


void dest_in_straight(int dir, int cn, int pc, int vc, int dx, int dy, int *dest_pc, int *dest_vc, int *is_blocked, int *credit)
{
    router_t *cur_router = &(router[cn]);
    int rs; // router status of the node in straight direction(dir).
    int i, p1, p2;
    int DN1 = (dir+3)%4; //     left direction relative to the dir.
    int DN2 = (dir+1)%4; //    right direction relative to the dir.
    int bdir = (dir+2)%4; // backward direction relative to the dir.
    int IN1[3] = {dir, DN1, bdir};
    int IN2[3] = {dir, DN2, bdir};
    int dir_avail[4];

    ////////////////////////////////////////
    // 1. Check forward direction first.
    ////////////////////////////////////////
    
    // Check whether forward node is destination node.
    int is_next_node_dest = (
        (dx ==  1 && dy ==  0 && dir == EAST)  || 
        (dx == -1 && dy ==  0 && dir == WEST)  ||
        (dx ==  0 && dy ==  1 && dir == NORTH) || 
        (dx ==  0 && dy == -1 && dir == SOUTH) 
      )? YES:NO;

    for(i=LEFT; i<= SOUTH; i++)
      dir_avail[i] = NO;

    // Check the status of the forward node.
    rs = router[cn].FA_neighbor_info[dir];
    
    if( (rs != FAIL && rs != WORSE) || (rs == WORSE && is_next_node_dest == YES) )
    //{ *dest_pc = dir; return; } // Yes, we can go straight.
    { dir_avail[dir] = YES; } // Yes, we can go straight.
    
    ////////////////////////////////////////
    // 2. We cannot go straight. 
    // Check left-side and right-side.
    ////////////////////////////////////////

    for(i=0; i<3; i++)
    {
      // Get path scores.
      p1 = router[cn].FA_direction_info[DN1][IN1[i]];
      p2 = router[cn].FA_direction_info[DN2][IN2[i]];
      
      // If both paths have score 3, we cannot use thme.
      // For the scoring details, see node_marking.c file.
      if(p1 == 3 && p2 == 3)
        continue;
    
      // A. If p1 has less score than p2, select DN1.
      //if(p1 < p2)      { *dest_pc = DN1; return; }
      if(p1 < p2)      { dir_avail[DN1] = YES; break;}
      
      // B. If p2 has less score than p1, select DN2.
      else if(p1 > p2) { dir_avail[DN2] = YES; break;}
      
      // C. Both p1 and p2 has same score.
      // Check buffer and distance for final routing decision.
      // Under fault-free environment, all routing decisions 
      // should be made here (both p1 and p2 are always 0).
      // Here, we don't consider the distance to destination 
      // since they're the same. (Dest is in straight direction 
      // and D1 and D2 are orthogonal to this direction.)
      //else { *dest_pc = (credit[DN1] >= credit[DN2])? DN1 : DN2; return; }
      else { dir_avail[(credit[DN1] >= credit[DN2])? DN1 : DN2] = YES; break;}

    }// for i

    if(dir_avail[dir] == YES ) *dest_pc = dir;
    else if(dir_avail[DN1] == YES) *dest_pc = DN1;
    else if(dir_avail[DN2] == YES) *dest_pc = DN2;
    /*
    if(dir_avail[dir] == YES && dir != pc) *dest_pc = dir;
    else if(dir_avail[DN1] == YES && DN1 != pc) *dest_pc = DN1;
    else if(dir_avail[DN2] == YES && DN2 != pc) *dest_pc = DN2;
    */
    else
    {
      ////////////////////////////////////////
      // 3. All the three directions (left, straight, right) are blocked.
      // If the only left direction(bdir) is also blocked, this flit is 
      // generated within trapped region which should be avoided in simulation.
      // If the bdir is available, that's the only option we have.
      // Go to the backward direction.
      ////////////////////////////////////////
      rs = router[cn].FA_neighbor_info[bdir];
      if(bdir != pc && rs != FAIL && rs != WORSE) *dest_pc = bdir;
      else                                        *dest_pc = pc; // backtracking

    }
    return;
}

void dest_in_diagonal(int DN1, int DN2, int cn, int pc, int vc, int dx, int dy, int *dest_pc, int *dest_vc, int *is_blocked, int *credit)
{
    int stage;
    int node = cn;
    int r1, r2; // router status of the nodes in left-side and right-side relative to the dir.
    int i, p1, p2, dist1, dist2;
    int blocked1, blocked2;
    int BDN1 = (DN1+(NUM_PC-NUM_NIC_PC)/2) % (NUM_PC-NUM_NIC_PC);
    int BDN2 = (DN2+(NUM_PC-NUM_NIC_PC)/2) % (NUM_PC-NUM_NIC_PC);
    int IN1[2][3] = { {DN2, DN1, BDN2}, {DN2, BDN1, BDN2}};
    int IN2[2][3] = { {DN1, DN2, BDN1}, {DN1, BDN2, BDN1}};
    int dir_avail[4];

    for(i=LEFT; i<= SOUTH; i++)
      dir_avail[i] = NO;

    router_t *cur_router = &(router[cn]);
    
    for(stage=0; stage<2; stage++)
    {
      for(i=0; i<3; i++)
      {
        p1 = router[cn].FA_direction_info[DN1][IN1[stage][i]];
        p2 = router[cn].FA_direction_info[DN2][IN2[stage][i]];

        // If both paths have score 3, we cannot use thme.
        // For the scoring details, see node_marking.c file.
        if(p1 == 3 && p2 == 3)
          continue;

        // A. If p1 has less score than p2, select DN1.
        //if(p1 < p2)      { *dest_pc = DN1; return; }
	if(p1 < p2)      { dir_avail[DN1] = YES; break;}
        
        // B. If p2 has less score than p1, select DN2.
        //else if(p1 > p2) { *dest_pc = DN2; return; }
	else if(p1 > p2) { dir_avail[DN2] = YES; break;}
        
        // C. Both p1 and p2 has same score.
        // Check buffer and distance for final routing decision.
        // Under fault-free environment, all routing decisions 
        // should be made here (both p1 and p2 are always 0).
        // Here, we need to consider the distance to destination 
        // since they might be different.
        else 
        { 
          //if     (credit[DN1] > credit[DN2]) *dest_pc = DN1;
          if     (credit[DN1] > credit[DN2]) { dir_avail[DN1] = YES; }
          //else if(credit[DN1] < credit[DN2]) *dest_pc = DN2;
          else if(credit[DN1] < credit[DN2]) { dir_avail[DN2] = YES; }
          else // Compare distance... Here...
          { 
            switch(DN1)
            {
              case WEST : {dist1 = -dx; break;}
              case NORTH: {dist1 =  dy; break;}
              case EAST : {dist1 =  dx; break;}
              case SOUTH: {dist1 = -dy; break;}
            }
            switch(DN2)
            {
              case WEST : {dist2 = -dx; break;}
              case NORTH: {dist2 =  dy; break;}
              case EAST : {dist2 =  dx; break;}
              case SOUTH: {dist2 = -dy; break;}
            }

            // In stage 0, both DN1 and DN2 are toward the destination.
            // Thus, choose direction with the longest distance.
            if(stage == 0)
              //*dest_pc = (dist1 >= dist2)? DN1:DN2; 
              dir_avail[(dist1 >= dist2)? DN1:DN2] = YES; 
            // In stage 1, both DN1 and DN2 are away from the destination.
            // Thus, choose direction with the shortest distance.
            else // stage == 1
              //*dest_pc = (dist1 <= dist2)? DN1:DN2; 
              dir_avail[(dist1 <= dist2)? DN1:DN2] = YES; 
          } 
          //return; 
          break; 
        }// else
      }// for i
      
     /* 
      if    (dir_avail[DN1] == YES && DN1 != pc ) {*dest_pc = DN1; return;}
      else if(dir_avail[DN2] == YES && DN2 != pc) {*dest_pc = DN2; return;}
      */
      if    (dir_avail[DN1] == YES ) {*dest_pc = DN1; return;}
      else if(dir_avail[DN2] == YES ) {*dest_pc = DN2; return;}
      else
      { // Switch to the backward directions.
	DN1 = BDN1; DN2 = BDN2;
      }

    }// for stage

    // Only backtracking path is available.
    *dest_pc = pc; 
    return;
}

void proximity_aware_route(int cn, int dn, int pc, int vc, int *dest_pc, int *dest_vc)
{
    int cur_x, cur_y, dest_x, dest_y, dx, dy; /* hold the coordinates of the current node */
    int credit[MAX_PC-MAX_NIC_PC], best_vc[MAX_PC-MAX_NIC_PC]; // number of available buffer
    int is_blocked[4];  // blocking state
    int xdir, ydir;

    /* Calculate cur and dest node coordinates */
    calc_coord(cn, &cur_x, &cur_y);
    calc_coord(dn, &dest_x, &dest_y);
    dx = dest_x - cur_x;    // offset to go right (negative value means left)
    dy = dest_y - cur_y;    // offset to go up    (negative value means down)

    ///////////////////////////////////////////////////////////////////////////////
    // Based on the router.FA_direction_info[][], make routing decision          //
    // (set new_pc and new_vc).                                                  //
    ///////////////////////////////////////////////////////////////////////////////

    // Check the maximum number of available buffer of VCs in a PC.
    get_best_credit(cn, credit, best_vc);
    /* Calculate blocked signals */
    get_blocked(cn, is_blocked);

    
    
    // 1.5 Check if escape VC.
    // Disable the code between two lines to test 
    // new deadlock recovery scheme.
    //  ------------------------------------------  
    if(topology == MESH)
    {
      xdir  = (dx > 0)? RIGHT : LEFT;    ydir  = (dy > 0)? UP : DOWN;   

      if(vc == 0 && (dx !=0 || dy !=0))
      { 
	*dest_pc = (dx != 0)? xdir : ydir;
	*dest_vc = vc; 
	return; 
      }
    }
    else if(topology == TORUS)
    {
      if(vc < 2)
      { 
	*dest_pc = (dx != 0)? xdir : ydir;
	*dest_vc = vc; 
	return;
      }
    }
    //  ------------------------------------------  
    
    

    // 1. Ejection at this node.
    if(dx == 0 && dy == 0)
      *dest_pc = THIS; // PC for EJECTION

    // 2. Go somewhere...
    else if(dx == 0 && dy  > 0)   dest_in_straight(NORTH,       cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);
    else if(dx  > 0 && dy  > 0)	  dest_in_diagonal(NORTH, EAST, cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);
    else if(dx  > 0 && dy == 0)	  dest_in_straight(EAST,        cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);
    else if(dx  > 0 && dy  < 0)	  dest_in_diagonal(EAST, SOUTH, cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);
    else if(dx == 0 && dy  < 0)	  dest_in_straight(SOUTH,       cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);
    else if(dx  < 0 && dy  < 0)	  dest_in_diagonal(SOUTH, WEST, cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);
    else if(dx  < 0 && dy == 0)	  dest_in_straight(WEST,        cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);
    else                      	  dest_in_diagonal(WEST, NORTH, cn, pc, vc, dx, dy, dest_pc, dest_vc, is_blocked, credit);

    // If no VCs have available buffer (best_vc[cur_dir] == -1), use the same VC as before.
    *dest_vc = (best_vc[*dest_pc] != -1)? best_vc[*dest_pc] : vc;

}

